COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00022 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A66.tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, October 1988}
\leftline{\sevenrm Unpublished draft}
\bigskip
\noindent{\bf Chapter 2: Definition of machine, standardize, simulate, \dots\hfil}
\smallskip
Computers and computer programs contain components that can hold information,
test~it, and operate on~it. For example, a~counter can hold an integer;
the counter
can test whether it contains zero; and it can increase or decrease its
content by one. A~clock holds an integer, and at every step increases its
content by one. Other such components are paper and magnetic tapes, random
access memories, pushdown stacks, lists, and queues. We will consider
certain such components, called {\it devices}, that are amenable to study with
the tools of mathematics.

A device has a {\it carrier}, the set of the values it may contain. A~{\it state\/}
of the device is an element of the carrier. The carrier of a counter,
for example, might be~{\bf Z}, the set of all integers, or~{\bf N}, the set
of all natural numbers (non-negative integers). 
A~device  has a {\it repertory},
a~set of relations on the carrier. For a counter with carrier~{\bf N},
the repertory might include ${\tt INCREMENT}(x)=x+1$, ${\tt DECREMENT}(x)=x-1$
(defined only for $x≠0$), ${\tt ZERO}(x)=x$ (defined only for $x=0$), and
${\tt NONZERO}(x)=x$ (defined only for $x≠0$). The repertory of a device
normally includes ${\tt NOOP}(x)=x$, an operation that does nothing,
but the example of a clock shows why {\tt NOOP} might not be in the
repertory. Operations in the repertory that are subsets of the identity
function, like {\tt ZERO} and {\tt NONZERO}, are called {\it tests}.
Ordinarily the union of two tests, or the complement of a test, is also a
test in the repertory.

A {\it machine\/} is a finite set of devices. For example, what is called
a two-counter transducer consists of a {\it control}, which has a finite
carrier; two counters,
each with its own repertory of {\tt INCREMENT}, {\tt DECREMENT}, etc.; and
an {\it input\/} and an {\it output}, each of which has as its carrier 
the set of strings over some alphabet.

A {\it configuration\/} of a machine is a specification of a state for
each device.  The set of configurations is therefore the cartesian
product of the carriers. When a machine goes to work, it~passes through
a finite or infinite sequence of configurations.

An {\it instruction\/} for a machine is a specification for each device
of an operation from its repertory.  An instruction can be applied to a
configuration if, for each device, the operation in the instruction can
be applied to the state in the configuration. If a machine has devices
$D↓1$, $D↓2$, and~$D↓3$, in respective states $x↓1$, $x↓2$, $x↓3$, then the
instruction $\langle f↓1, f↓2, f↓3 \rangle$
changes the current configuration 
$\langle x↓1, x↓2, x↓3 \rangle$
into its {\it sequel} $\langle x↓1f↓1, x↓2f↓2, x↓3f↓3 \rangle$,
provided all are defined. Every instruction is a relation on the
configurations of a machine.

A {\it program} for a machine is a finite set of instructions.  A
{\it trace} of a program $P$ is a sequence of configurations 
$\langle C↓0, C↓1, \ldots, C↓n \rangle$, where for each $j$ $(1 \leq j \leq n)$
there is an instruction $I\in P$ for which the relation $C↓{j-1}I$ $C↓j$ holds. 
A machine has a set $X = X↓M$ of possible {\it arguments}, and an {\it initial}
{\it relation} $\alpha$; $C↓0$ may be the initial configuration with argument
$x \in X$ if $x \alpha C↓0$.  Similarly, there is set $Y = Y↓M$ of possible
{\it results}, and a {\it final relation} $\omega$; $C↓n$ may be the final
configuration with result $y \in Y$ if $C↓n \omega y$.  The relation $\alpha$ is
defined in terms of an initial relation $\alpha↓d$ for each device $d$ 
of the machine; $x \alpha \langle u↓1, u↓2, \ldots, u↓k \rangle = C↓0$ if
for each $d$, $x \alpha↓d u↓d$.  Similarly, $C↓n \langle v↓1, v↓2, \dots,
v↓d \rangle \omega y$ if for each $d$, $v↓d \omega↓d t$.

If operations of a program and the initial and final relation of the machine
are all partial functions, and if the instructions of the program and the final
relation all have disjoint domains, it follows that for each argument there is at
most one computation and one result.  Such a program is called {\it deterministic}.

For example, consider this flowchart:

\bigskip
$$\vcenter{\halign{\hfil#\hfil\quad%
&\hfil#\hfil\quad%
&\hfil#\hfil\quad%
&\hfil#\hfil\quad%
&\hfil#\hfil\quad%
&\hfil#\hfil\quad%
&\hfil#\hfil\quad%
&\hfil#\hfil\quad%
&\hfil#\hfil\cr
&{\tt START}\cr
\noalign{\bigskip}
&$x←0$\cr
\noalign{\bigskip}
\noalign{\bigskip}
&2\cr
\noalign{\bigskip}
&&{\tt EOF}\cr
&{\tt READ} $C$&&&6&&$x=0$ ?\cr
\noalign{\bigskip}
&3&&&&$Y$&&$N$\cr
\noalign{\bigskip}
&$C=?$&&&&7&&8\cr
\noalign{\bigskip}
$a$&&$b$&&&{\tt PRINT}&&{\tt PRINT}\cr
&&&&&``{\tt{ACCEPT}}''&&``{\tt{REJECT}}''\cr
\noalign{\bigskip}
4&&5&&&&9\cr
\noalign{\bigskip}
$x←x+1$&&$x←x-1$&&&&{\tt HALT}\cr}}$$

\bigskip
\bigskip
A machine that could perform this algorithm has a control device with 
states~1 to~9; a~counter with carrier~{\bf Z}; and an input device that
holds a string (file) of $a$'s and~$b$'s. A~program for this machine to
carry out the algorithm is
$$\vcenter{\halign{\quad\hfil#\hfil\qquad&#\hfil\qquad&#\hfil\qquad&#\hfil\quad\cr
{\tt CONTROL}&{\tt INPUT}&{\tt COUNTER}&comments\cr
\noalign{\medskip}
\noalign{\hrule}
\noalign{\medskip}
$\langle 1,2\rangle\,,$&{\tt NOOP},&{\tt NOOP}&Initial state of counter is zero\cr
$\langle 2,4\rangle\,,$&{\tt SCAN} $a$,&{\tt NOOP}&Variable $C$ not needed\cr
$\langle 4,2\rangle\,,$&{\tt NOOP},&{\tt INCREMENT}&Counter contains $x$\cr
$\langle 2,5\rangle\,,$&{\tt SCAN} $b$,&{\tt NOOP}\cr
$\langle 5,2\rangle\,,$&{\tt NOOP},&{\tt DECREMENT}\cr
$\langle 2,6\rangle\,,$&{\tt EOF},&{\tt NOOP}\cr
$\langle 6,7\rangle\,,$&{\tt NOOP},&{\tt ZERO}\cr
$\langle 6,8\rangle\,,$&{\tt NOOP},&{\tt NONZERO}\cr}}$$
where 1 is the initial control state, and 7 is the final control state. The
initial and final states of the input are $\{a,b\}↑{\ast}$, although
this particular program only halts when the state of the input is the
empty string. The initial state of the counter is zero, the final states
are~{\bf Z}.

A much shorter program that does not correspond to any traditional flowchart,
but meets the definitions used here, is:
$$\vcenter{\halign{\hfil#\hfil\qquad&#\hfil\qquad&#\hfil\cr
$\langle 2,2\rangle\,,$&{\tt SCAN} $a$,&{\tt INCREASE}\cr
$\langle 2,2\rangle\,,$&{\tt SCAN} $b$,&{\tt DECREASE}\cr
$\langle 2,7\rangle\,,$&{\tt EOF},&{\tt ZERO}\cr}}$$
Rather than use traditional flowcharts, we will present programs pictorially
by labeled digraphs, with control states as vertices. An instruction with
$\langle i,j\rangle$ as its control operation is shown as an arc
from~$i$ to~$j$, labeled with all other operations of the instruction
except {\tt NOOP}s. Initial control states are marked by~$\Rightarrow$,
accepting control states by a plus sign. The two programs above are presented
by the following graphs:

\vfill\eject
\noindent
For input $ab$, the trace of the first program is:
$$\vcenter{\halign{\quad\hfil$#$\hfil\qquad&$#$\hfil\qquad&#\hfil\qquad&#\hfil\quad\cr
{\tt CONFIGURATION}&{\tt CONTROL}&{\tt INPUT}&{\tt COUNTER}\cr
\noalign{\medskip}
\noalign{\hrule}
\noalign{\medskip}
1,ab,0 & \langle 1,2\rangle\cr
2,ab,0 & \langle 2,4\rangle &{\tt SCAN} $a$\cr
4,b,0  & \langle 4,2\rangle &        &{\tt INCREMENT}\cr
2,b,1  & \langle 2,5\rangle &{\tt SCAN} $b$\cr
5,\Lambda,1 & \langle 5,2\rangle &   &{\tt DECREMENT}\cr
2,\Lambda,0 & \langle 2,6\rangle &{\tt EOF}\cr
6,\Lambda,0 & \langle 6,7\rangle &   &{\tt ZERO}\cr
7,\Lambda,0\cr
}}$$

Next we define in detail all the types of device we will study.

A {\it control\/} has any finite set, usually called~$Q$, as its carrier.
The repertory consists of all partial functions on~$Q$. Usually, people
use only functions that map some particular $i\in Q$ into some particular
$j\in Q$, and are undefined elsewhere, i.e., functions graphed by
$\{\langle i,j\rangle\}$. Machines have control devices so frequently
that most books include a control device in the definition of a machine.

A {\it finite store\/} has a finite set $F$ as its carrier. If $x$ names the
state of a finite store, the repertory contains $x←a$, i.e., the
constant function $F\times\{a\}$; $x=a$, i.e., the test
$\{\langle a,a\rangle\}$; and the complementary test $x≠a$.

A {\it signed counter} has carrier~{\bf Z}. The repertory, where 
$x$ names the state 
of the counter,~is

\smallskip
\halign{\qquad\qquad{\tt #}\hfil\qquad&#\hfil\cr
INCREMENT&$\{\langle x,x+1\rangle\}$\cr
DECREMENT&$\{\langle x+1,x\rangle\}={\tt INCREMENT}↑{-1}$\cr
ZERO&$\{\langle 0,0\rangle\}$\cr
POSITIVE&$\{\langle x,x\rangle$ where $x>0\}$\cr
NEGATIVE&$\{\langle x,x\rangle$ where $x<0\}$\cr}

\smallskip
An {\it unsigned counter} has carrier~{\bf N}. The repertory is

\smallskip
\halign{\qquad\qquad{\tt #}\hfil\qquad&#\hfil\cr
INCREMENT&$\{\langle x,x+1\rangle\}$\cr
DECREMENT&$\{\langle x+1,x\rangle\}={\tt INCREMENT}↑{-1}$, defined for $x≥1$\cr
ZERO&$\{\langle 0,0\rangle\}$\cr
NONZERO&$\{\langle x,x\rangle$ where $x≠0\}=\{\langle x+1, x+1\rangle \}$\cr
DIMINISH&${\tt DECREMENT}\cup{\tt ZERO}=\{\langle x,\max(x-1,0)\rangle\}$.\cr}

\smallskip
A ({\it right}) {\it stack} has carrier $\Sigma↑{\ast}$ for some finite $\Sigma$.
The repertory is (where each~$a$ is a fixed element of~$\Sigma$):

\smallskip
\halign{\qquad\qquad{\tt #}\hfil\qquad&#\hfil\cr
PUSH $a$&$\{\langle x,xa\rangle\}$\cr
POP $a$&$({\tt PUSH}\>a)↑{-1} = \{\langle x a, x \rangle\}$\cr
${\tt TOP}=a$&$\{\langle xa,xa\rangle\}$\cr
POP&$\bigcup↓a\,${\tt POP} $a$, undefined for $\Lambda$\cr
EMPTY&$\{\langle\Lambda,\Lambda\rangle\}$.\cr}

\smallskip
A {\it left stack} uses the conjugate operations under reflection of the contents.
That is, it operates on the left end of the contents.

A {\it queue\/} has carrier $\Sigma↑{\ast}$ for finite~$\Sigma$. The repertory
(where each~$a$ is a fixed element of~$\Sigma$):

\smallskip
\halign{\qquad\qquad{\tt #}\hfil\qquad&#\hfil\cr
APPEND $a$&$\{\langle x,xa\rangle\}$\cr
DELETE $a$&$\{\langle ax,x\rangle\}$\cr
EMPTY&$\{\langle\Lambda,\Lambda\rangle\}$\cr}

\smallskip
A {\it tape\/} has carrier $\Sigma↑{\ast}\times\Sigma↑{\ast}$ for finite~$\Sigma$.

\smallskip
\halign{\qquad\qquad{\tt #}\hfil\qquad&#\hfil\cr
GO RIGHT&$\{\langle x,ay\rangle\,,\,\langle xa,y\rangle\}\cup\{\langle x,\Lambda%
\rangle\,,\,\langle x{\spa},\Lambda\rangle\}$\cr
GO LEFT&is conjugate to {\tt GO RIGHT}\cr
PRINT $a$ RIGHT&$\{\langle x,by\rangle\,,\,\langle x,ay\rangle\}\cup\{\langle
x,\Lambda\rangle\,,\,\langle x,a\rangle\}$\cr
PRINT $a$ LEFT&another  conjugate $\left\{\vcenter{\halign{{\tt #}\hfil\cr
GO LEFT\cr
PRINT $a$ RIGHT\cr
GO RIGHT\cr}}\right\}$\cr
$a$ ON RIGHT&$\{\langle x,ay\rangle\,,\,\langle x,ay\rangle\}\quad a≠\spa$\cr
$\spa$ ON RIGHT&$\{\langle x,{\spa}y\rangle\,,\,\langle x,{\spa}y\rangle\}\cup
\{\langle x,\Lambda\rangle\,,\,\langle x,\Lambda\rangle\}$.\cr}

\smallskip
An {\it input\/} has carrier $\Sigma↑{\ast}$.

\smallskip
\halign{\qquad\qquad{\tt #}\hfil\qquad&#\hfil\cr
SCAN $a$&$\{\langle ax, x\rangle \}$\cr
EOF&$\langle \Lambda, \Lambda\rangle\}$\cr}

\smallskip
An {\it output\/} has carrier $\Sigma↑{\ast}$.

\smallskip
\halign{\qquad\qquad{\tt #}\hfil\qquad&#\hfil\cr
WRITE $a$&$\{x,xa\}$.\cr}
\bye